#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#define END -1 
typedef struct ENode *Edge;
struct ENode
{
	int adjvex;
	int seq; //编号
	Edge next;
};
typedef struct VNode *Vertex;
struct VNode
{
	int seq;
	Edge link;
};
typedef struct ANode *Adjlist;
struct ANode
{
	int size;
	Vertex list;
};
 
Adjlist Create_Adjlist(int n)
{
	Adjlist adjlist = (Adjlist)malloc(sizeof(struct ANode));
	adjlist->list = (Vertex)malloc(n*sizeof(struct VNode)); 
	adjlist->size = n;
	for(int i=0;i<n;i++)
	{
		adjlist->list[i].seq = i;
		adjlist->list[i].link = NULL;
	}
	return adjlist;
}
 
void Insert_Edge(int seq, Vertex head, int end)
{
	Edge rear = head->link;
	Edge newEdge = (Edge)malloc(sizeof(struct ENode));
	
	newEdge->seq = seq;
	newEdge->adjvex = end;
	newEdge->next = NULL;
	if (rear == NULL) 
		head->link = newEdge; 
	else 
	{
		while(rear->next != NULL) rear = rear->next; //插到尾巴上
		rear->next = newEdge;
	}
}
 
void Print_Path(int path[])
{
	int i = 0;
	while (path[i + 1] != END)
		printf("%d ", path[i++]);
	printf("%d\n", path[i]);
}
 
void DFS(int start, int depth, Adjlist adjlist, int path[], int visited[])
{
	if(start == adjlist->size - 1)
	{
		path[depth] = END;
		Print_Path(path);
		return;
	}
	else
	{
		if(!visited[start])
		{
			visited[start] = 1;
			Edge link = adjlist->list[start].link;
			while(link != NULL)
			{
				path[depth] = link->seq;
				DFS(link->adjvex, depth + 1, adjlist, path, visited);
				link = link->next;
			}
			visited[start] = 0;
			return;
		}
	}
}
 
void Iterate_Path(Adjlist adjlist)
{
    int path[adjlist->size], visited[adjlist->size];
    memset(visited, 0, adjlist->size*sizeof(int));
	DFS(0, 0, adjlist, path, visited);
}
 
int main()
{
	Adjlist LGraph;
	int Nv, Ne;
	int seq,v1,v2;
	scanf("%d%d",&Nv, &Ne);
	LGraph = Create_Adjlist(Nv);
	for(int i=0;i<Ne;i++)
	{
		scanf("%d%d%d", &seq, &v1, &v2);
		Insert_Edge(seq, &(LGraph->list[v1]), v2);
		Insert_Edge(seq, &(LGraph->list[v2]), v1);
	}
	Iterate_Path(LGraph);
	return 0;
}